package com.zp.self.module.level_4_算法练习.算法.排序.算法题;

import com.zp.self.module.level_4_算法练习.数据结构.链表.ListNode;
import org.junit.Test;

/**
 * @author By ZengPeng
 */
public class 力扣_148_排序链表 {
    @Test
    public void main() {

        ListNode listNode = sortList(ListNode.getNode());
        System.out.println(listNode);
    }

    /**
    题目：给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

     示例 1：
     输入：head = [4,2,1,3]
     输出：[1,2,3,4]
     示例 2：

     输入：head = [-1,5,3,4,0]
     输出：[-1,0,3,4,5]

     示例 3：
     输入：head = []
     输出：[]

     #进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

    分析：【BR 💔💔💔💔💔💔】
       大神:归并排序--非递归版本:  bottom-to-up
             bottom-to-up 的归并思路是这样的：先两个两个的 merge，完成一趟后，再 4 个4个的 merge，直到结束。
             举个简单的例子：[4,3,1,7,8,9,2,11,5,6].
                 step=1: (3->4)->(1->7)->(8->9)->(2->11)->(5->6)
                 step=2: (1->3->4->7)->(2->8->9->11)->(5->6)
                 step=4: (1->2->3->4->7->8->9->11)->(5->6)
                 step=8: (1->2->3->4->5->6->7->8->9->11)-
            实现步骤:
             a.不断按2的n次方为距离扩大截断链表cat(l,n),
                    left = cur;
                    right = cut(left, size); // left->@->@ right->@->@->@...
                    cur = cut(right, size); // left->@->@ right->@->@  cur->@->...
             b.将截断的链表进行合并 merge(left, right)，返回头节点;
             c.遍历合并后的链表，找到末尾节点，后续有用
            --执行用时：15 ms, 在所有 Java 提交中击败了17.19%的用户  --时间、空间复杂度 O(n*logn)、O(1)
       快速排序:创建集合记录所有节点，根据节点排序，重新组装链表的next
                --时间、空间复杂度 O(n*logn)、O(n)  --不符合常数级空间复杂度

    边界值 & 注意点：
       1.
     **/
    public ListNode sortList(ListNode head) {
        int length =0;
        ListNode virtual = new ListNode(),cur,left,right,tail;
        virtual.next=head;
        while (head!=null){
            head=head.next;
            length++;
        }
        for (int size = 1; size <length; size*=2) {
            cur=virtual.next;//每次扩大分治范围时，重新从起点开始
            tail=virtual;
            while (cur!=null){
                //a.不断按2的n次方为距离扩大截断链表cat(l,n),
                left = cur;
                right = cut(left,size);//得到左树
                cur = cut(right,size);//得到右数，并得到剩余节点
                //b.将截断的链表进行合并 merge(left, right)，返回头节点;
                tail.next= merge(left,right);
                //c.遍历合并后的链表，找到末尾节点，后续有用
                while (tail.next!=null)
                    tail=tail.next;
            }
        }
        return virtual.next;
    }



    /**
     * Description: 将cur链表的前面size个留住，后面的阶段，返回后面段的
     * @param cur 当前链表
     * @param size 需要的个数
     */
    private ListNode cut(ListNode cur, int size) {
        ListNode next=cur;
        while (--size>0 && next!=null)
            next = next.next;
        if(next==null)
            return null;
        ListNode res = next.next;
        next.next=null;
        return  res;
    }

    /**
     * Description: 合并两个链表
     * @param left 链表
     * @param right 链表
     */
    private ListNode merge(ListNode left, ListNode right) {
        if(right==null)return left;
        ListNode pro ,res;
        if(left.val>right.val){
            pro=right;
            right=right.next;
        }else {
            pro=left;
            left=left.next;
        }
        res=pro;
        while (left!=null && right!=null){
            if(left.val>right.val){
                pro.next=right;
                pro=right;
                right=right.next;
            }else {
                pro.next=left;
                pro=left;
                left=left.next;
            }
        }
        pro.next=left==null?right:left;
        return res;
    }
}
